Coefficient de pulvérisation \(N(l)\) d'une famille \(\mathcal C\subset{\mathcal P}(\mathcal X)\)
Nombre maximal de traces (intersections) distinctes que peuvent faire les éléments de \(\mathcal C\) avec un sous-ensemble de \(\mathcal X\) de cardinal \(l\). $$N(l):=\max_{x_1,\dots,x_l\in\mathcal X}\lvert\{\{x_1,\dots,x_l\}\cap C\mid C\in\mathcal C\}\rvert$$

• majoration grossière : \(N(l)\leqslant\) \(2^l\)
• on a \(N(l+m)\leqslant\) \(N(l)N(m)\)

Coefficient de pulvérisation \(N_\mathcal S(l)\) de \(\mathcal S\) famille de Fonction de décisions qui sont des indicatrices
Coefficient de pulvérisation de la famille \(\mathcal C=\{C\mid\exists g\in\mathcal S,g=\Bbb 1_C\}\).

• on appelle fonction de croissance de \(\mathcal S\) la fonction \(l\mapsto N_\mathcal S(l)\)
• dans le cas où \(\mathcal Y=\{-1,1\}\), on étend la définition en prenant \(\mathcal C=\) \(\{C\mid\exists g\in\mathcal S,C=\{x\in\mathcal X\mid g(x)\gt 0\}\}\)
• si \(\mathcal S\) est une classe de Fonction de décisions formées de fonctions indicatrices tq sa Dimension de Vapnik-Chervonenkis \(\operatorname{dim}_\text{VC}(\mathcal S)\) est égale à \(h\lt +\infty\), alors on a...
    
• \(\forall l\geqslant1,\) \(N_\mathcal S(l)\) \(\leqslant(l+1)^h\)
    
• \(\forall l\geqslant h\), \(N_\mathcal S(l)\) \(\leqslant(\frac{el}h)^h\)

START
Ω Basique (+inversé optionnel)
Recto: Que décrit le coefficient de pulvérisation de \(\mathcal S\) ?
Verso: Il décrit la capacité de \(\mathcal S\) à séparer des ensembles de points.
Bonus:
Carte inversée ?:
END